← All Articles

[SW Expert Academy] 1949. 등산로 조성

Posted on

문제 :

등산로를 조성하려고 한다.등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.등산로 부지는 아래 [Fig. 1]과 같이 숫자가 표시된 지도로 주어지며, 각 숫자는 지형의 높이를 나타낸다.

image

등산로를 만드는 규칙은 다음과 같다.

① 등산로는 가장 높은 봉우리에서 시작해야 한다.

② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.

즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.

③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.

N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.

이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.


제약사항 :

  1. 시간 제한 : 최대 51개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초
  2. 지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)
  3. 최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)
  4. 지도에 나타나는 지형의 높이는 1 이상 20 이하의 정수이다.
  5. 지도에서 가장 높은 봉우리는 최대 5개이다.
  6. 지형은 정수 단위로만 깎을 수 있다.
  7. 필요한 경우 지형을 깎아 높이를 1보다 작게 만드는 것도 가능하다.

입력 :

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.

그 다음 N개의 줄에는 N * N 크기의 지도 정보가 주어진다.


출력 :

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 “#t”로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.



풀이 :

문제는 벽 부수기와 같이 예외 상황을 정수번 통과할 수 있게끔 경로를 탐색하는 전형적인 문제이다.

bfs보단 dfs로 접근할 경우 등산로 경로를 탐색할 때 visit 체크를 좀 더 효과적으로 할 수 있는 듯 하다.

딱 한 번에 한해 높이를 깎을 수 있다는 말은 한 번에 한해서 높이가 같거나 낮은 곳을 지나칠 수 있다는 말이다.

따라서 dfs를 탐색할 때 isdig라는 boolean 변수를 두고 깎은 적이 있는지 없는지 판단해 가면서 경로를 탐색하면 문제를 해결할 수 있다.

그 외에 dfs 구현은 여느 문제와 동일하게 진행하면 풀이가 가능했다.



코드 :

코드 보기/접기 
#include <iostream>
#include <algorithm>

using namespace std;
int n, dignum, map[8][8], di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};
bool visit[8][8];

int findLongestPath(int curx, int cury, int height, int curcnt, bool isdig) {
    visit[curx][cury] = true;

    int dist = curcnt;
    for (int k = 0; k < 4; k++) {
        int cmpx = curx + di[k], cmpy = cury + dj[k];
        if (cmpx < 0 || cmpx >= n || cmpy < 0 || cmpy >= n) continue;
        if (visit[cmpx][cmpy]) continue;
        if (map[cmpx][cmpy] >= height) {
            if (!isdig || map[cmpx][cmpy] - dignum >= height) continue;
            dist = max(dist, findLongestPath(cmpx, cmpy, height - 1, curcnt + 1, false));
        } else {
            dist = max(dist, findLongestPath(cmpx, cmpy, map[cmpx][cmpy], curcnt + 1, isdig));
        }
    }

    visit[curx][cury] = false;
    return dist;
}

void testCase(int curidx) {
    int maxnum = 0, maxdist = 0;
    cin >> n >> dignum;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            maxnum = max(map[i][j], maxnum);
        }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (map[i][j] == maxnum)
                maxdist = max(maxdist, findLongestPath(i, j, maxnum, 1, true));

    cout << '#' << curidx << ' ' << maxdist << '\n';
}

int main() {
    int tc;
    cin >> tc;
    for (int i = 1; i <= tc; i++)
        testCase(i);
    return 0;
}


AlgorithmalgorithmSW ExpertC++